//
// Created by 麻再挺 on 2021/12/16.
//

#include "search_graph.h"
#include "./../stack_queue/queue.h"

/**
 * 深度有限搜索算法
 * @param g 图
 * @param v 值
 */
void DFS(SMGraph g, int index);

/**
 * 初始搜索图
 * @param g 图
 */
void CreateSDN(SMGraph *g, int vexNum, int arcNum, int arr[]){
    // 赋值图顶点数
    g->vexNum = vexNum;
    // 赋值弧数
    g->arcNum = arcNum;
    // 依次对顶点本身赋值
    for (int i = 0; i < g->vexNum; ++i) {
        g->vex[i] = i + 1;
    }
    // 初始化二维矩阵, 全部归 0, 指针为 NULL
    for (int i = 0; i < g->vexNum; ++i) {
        for (int j = 0; j < g->vexNum; ++j) {
            // 赋值源数据
            g->arcs[i][j].adj = 0;
            // 赋值信息
            g->arcs[i][j].info = NULL;
        }
    }
    // 向二维数组中添加弧的数据
    for (int i = 0; i < g->arcNum; ++i) {
        // 弧头弧尾
        int v1 = arr[2 * i];
        int v2 = arr[2 * i + 1];
        // 确定顶点位置
        int m = LocateSVex(g, v1);
        int n = LocateSVex(g, v2);
        //排除错误数据
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        // 将正确的弧加入二维数组
        g->arcs[m][n].adj = 1;
        g->arcs[n][m].adj = 1;
    }
}

/**
 * 深度优先搜索
 */
void DFSTraverse(SMGraph g) {
    // 将要标记的数组初始化为false
    for (int i = 0; i < g.vexNum; ++i) {
        visited[i] = false;
    }
    // 每个标记为false的顶点调用深度优先搜索函数
    for (int i = 0; i < g.vexNum; ++i) {
        // 如果没有被访问过, 则调用深度有限进行搜索
        if (!visited[i]) {
            DFS(g, i);
        }
    }
}

void DFS(SMGraph g, int index) {
    // 标记为已访问
    visited[index] = true;
    // 访问第 v 个结点
    visitVex(g, index);
    // 从顶点的第一条边开始, 到最后一条边, 对处于另一端的顶点调用DFS函数
    for (int i = FirstAdjVex(g, index); i >= 0; i = NextAjdVex(g, index, i)) {
        if (!visited[i]) {
            DFS(g, i);
        }
    }
}

int NextAjdVex(SMGraph g, int index, int curInx) {
    // 查找与数组下标为 v 的顶点之间的顶点, 返回它在数组中的下标
    for (int i = curInx + 1; i < g.vexNum; ++i) {
        // 如果有值, 说明是边
        if (g.arcs[index][i].adj) {
            return i;
        }
    }
    return -1;
}

int FirstAdjVex(SMGraph g, int index) {
    // 查找与数组下标为 v 的顶点之间的顶点, 返回它在数组中的下标
    for (int i = 0; i < g.vexNum; ++i) {
        // 如果有值, 说明是边
        if (g.arcs[index][i].adj) {
            return i;
        }
    }
    return -1;
}

void visitVex(SMGraph g, int index) {
    printf("%d ", g.vex[index]);
}

int LocateSVex(SMGraph *g, int v) {
    int i = 0;
    for (; i < g->vexNum; ++i) {
        if (g->vex[i] == v) {
            break;
        }
    }
    // 找不到的情况
    if (i > g->vexNum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}

/**
 * 打印图
 * @param g 图
 */
void PrintSGraph(SMGraph g) {
    for (int i = 0; i < g.vexNum; i++) {
        for (int j = 0; j < g.vexNum; j++) {
            int num = g.arcs[i][j].adj;
            if (num == 0) {
                printf("%s ", "∞");
            } else {
                printf("%d ", num);
            }
        }
        printf("\n");
    }
}

void BFSTraverse(SMGraph g) {
    // 将要标记的数组初始化为false
    for (int i = 0; i < g.vexNum; ++i) {
        visited[i] = false;
    }
    // 对于每个标记为 false 的顶点调用广度优先搜索算法
    LinkQueue q;
    Link_Queue_Init(&q);
    for (int i = 0; i < g.vexNum; ++i) {
        // 未访问的
        if (!visited[i]) {
            visited[i] = true;
            visitVex(g, i);
            // 入队
            Link_Queue_Enter(&q, &g.vex[i]);
            // 如果队列不为空, 则继续查询
            while (!Link_Queue_Empty(&q)) {
                // 取出队列的值
                QElemType e;
                Link_Queue_Deter(&q, &e);
                int v = *(int *)e;
                // 查找位置
                v = LocateSVex(&g, v);
                // 循环入队
                for (int j = FirstAdjVex(g, v); j >= 0; j = NextAjdVex(g, v, j)) {
                    if (!visited[j]) {
                        visited[j]=true;
                        visitVex(g, j);
                        Link_Queue_Enter(&q, &g.vex[j]);
                    }
                }
            }

        }
    }
}
